package LimitedTimeGame.Day_0217;

/**
 * @author zxc
 * @date 2023/02/17 16:31
 **/
/**
 * 题目 ：数值的整数次方
 * 题目详述 ：
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
 *
 * 提示：
 * -100.0 < x < 100.0
 * -231 <= n <= 231-1
 * -104 <= xn <= 104
 *
 */
public class MyPow03 {
    public static void main(String[] args) {
        System.out.println(myPow(2.0, 12));
    }
    /**
     * 思路 ：
     * 快速幂 + 迭代,来实现当前数x的幂运算;
     * ===》
     * 即，所要累加的幂值的二进制形式 与 所要累加的x^n次方相互对应
     * （1）即，从 x^1 ~ x^(2^n) 进行遍历 && 幂值n的二进制形式 低位(第1位)到高位（第n位）进行遍历,两者相互对应;
     * （2）若是当前遍历幂值的二进制位上，数字为1的话，则需要将与二进制位对应的x^n，累加到变量result中;
     *
     * @param x
     * @param n
     * @return
     */
    public static double myPow(double x, int n) {
        // 特殊情况 ：若是n == 0的话，则无论n为何值，其幂运算的结果都是1;
        if(n == 0 || x == 1){
            return 1;
        }
        long m = n;
        return m > 0 ? iteration(x , m) : 1 / iteration(x , -m);
    }

//    private static double iteration(double x, long n) {
//        //
//        double temp = 1.0;
//        double count = x;
//        while(n > 0){
//            System.out.println(n);
//            if((n % 2) == 1){
//                temp *= count;
//            }
//            count *= count;
//            n = n / 2;
//        }
//        return temp;
//    }
    private static double iteration(double x, long n) {
        // 保存迭代运算结果;
        double temp = 1.0;
        // 使用变量count，来保存 x^(x^n)的结果;
        double count = x;
        while(n > 0){
            // 若是幂值n的二进制形式的最底位 == 1的话，则选择将x^(x^n)累乘到temp;
            if((n & 1) == 1){
                temp *= count;
            }
            // 即，无论是都进行累乘操作，都会将count *= count;
            count *= count;
            // 即，位运算 ：类似于 n = n / 2;
            n = n >> 1;
        }
        return temp;
    }
    /**
     * 分析 ：
     * ===》
     * 即，若是采用迭代 + 快速幂，去计算当前pow(x,n)的话，
     * （1）所需要的时间复杂度 ：O（logn）;
     * （2）同时，需要O（1)空间复杂度;
     */
}
